package dp;

public class D230820 {

    // 最长回文子串

    // 中心扩展法 (贪心思想)
    // 时间：O(N2)
    // 空间：O(1)
    // 遍历字符串每个字符
    // 以每个字符为中心（分奇数和偶数的情况（bab, baab）），向两边扩展
    // 如果两边相同就是回文，扩展到最大长度，
    // 就是这个字符为中心的最长回文子串
    // 记录最大值即可
    public int fun(String s, int begin, int end){
        // 每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
            begin--;
            end++;
        }
        // 返回长度
        return end - begin - 1;
    }
    public int getLongestPalindrome (String A) {
        int maxlen = 1;
        // 以每个点为中心
        for(int i = 0; i < A.length() - 1; i++)
            // 分奇数长度和偶数长度向两边扩展
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1)));
        return maxlen;
    }


}
